package com.leetcode.algorithm.y22.m06;

import java.util.List;

/**
 * 1301. 最大得分的路径数目
 * 
 * https://leetcode.cn/problems/number-of-paths-with-max-score/
 * 
 * @author jie.deng
 *
 */
class Question1301Solution01 {

	/**
	 * 2 <= board.length == board[i].length <= 100
	 * 
	 * @param board
	 * @return
	 */
	public int[] pathsWithMaxScore(List<String> board) {
		// 从数组最右下方的字符 'S' 出发,到达数组最左上角的字符 'E'
		int len = board.size();
		int mod = 1000000007;
		int INVALID_SUM = -1;
		// dp状态定义：
		// sum[i][j] 路径上所有数字的和的最大值
		// cnt[i][j] 最大得分的方案数
		int[][] sum = new int[len][len];
		int[][] cnt = new int[len][len];
		sum[len - 1][len - 1] = 0;
		cnt[len - 1][len - 1] = 1;
		for (int i = len - 2; i >= 0; i--) {
			// 最后一行，只能是向左移动得来
			char ch = board.get(len - 1).charAt(i);
			if (ch == 'X' || sum[len - 1][i + 1] == INVALID_SUM) {
				sum[len - 1][i] = INVALID_SUM;
				cnt[len - 1][i] = 0;
				continue;
			}
			ch = ch == 'E' ? '0' : ch;
			sum[len - 1][i] = sum[len - 1][i + 1] + (ch - '0');
			cnt[len - 1][i] = cnt[len - 1][i + 1];
		}
		for (int i = len - 2; i >= 0; i--) {
			// 最右一行，只能是向上移动得来
			char ch = board.get(i).charAt(len - 1);
			if (ch == 'X' || sum[i + 1][len - 1] == INVALID_SUM) {
				sum[i][len - 1] = INVALID_SUM;
				cnt[i][len - 1] = 0;
				continue;
			}
			ch = ch == 'E' ? '0' : ch;
			sum[i][len - 1] = sum[i + 1][len - 1] + (ch - '0');
			cnt[i][len - 1] = cnt[i + 1][len - 1];
		}

		// ch[i][j]:ch[i+1][j+1], ch[i+1][j], ch[i][j+1]
		// dp状态初始化
		for (int i = len - 2; i >= 0; i--) {
			for (int j = len - 2; j >= 0; j--) {
				char ch = board.get(i).charAt(j);
				if (ch == 'X') {
					sum[i][j] = INVALID_SUM;
					cnt[i][j] = 0;
					continue;
				}

				int maxSum = Math.max(sum[i + 1][j + 1], sum[i + 1][j]);
				maxSum = Math.max(maxSum, sum[i][j + 1]);
				if (maxSum != INVALID_SUM) {
					ch = ch == 'E' ? '0' : ch;
					sum[i][j] = maxSum + (ch - '0');
					if (maxSum == sum[i + 1][j + 1]) {
						cnt[i][j] += cnt[i + 1][j + 1];
						cnt[i][j] %= mod;
					}
					if (maxSum == sum[i + 1][j]) {
						cnt[i][j] += cnt[i + 1][j];
						cnt[i][j] %= mod;
					}
					if (maxSum == sum[i][j + 1]) {
						cnt[i][j] += cnt[i][j + 1];
						cnt[i][j] %= mod;
					}
				} else {
					sum[i][j] = INVALID_SUM;
					cnt[i][j] = 0;
				}
			}
		}
		if (sum[0][0] == INVALID_SUM) {
			return new int[] { 0, 0 };
		}
		return new int[] { sum[0][0] %= mod, cnt[0][0] };
	}

}